package greedy;

/**
 * 示例：7.0.9.6.9.6.1.7.9.0.1.2.9.0.3
 *
 * 如何理解这个代码呢？
 * step好理解，代表到达终点我们需要几步，这个步数从零开始
 *
 * end表示第step时，我们可以落脚的范围，比如我们的例子中，第0步，我们处在索引0
 * 此时我们动弹不得，落脚范围就是[0,0]
 * 那我们走第一步，显然我们可以往后走七步，那么我们end就为7，意思是我们第一步落脚范围为[1,7]
 *
 * farthest如何理解。我的理解他就是你下一步可以抵达的最远范围。
 * 还是这个例子，你走第一步，只能落脚在[1,7]的范围中，那么你应该落脚到哪个点上去呢？显然，哪个点能让你跑的最远，你就去哪个点
 * 在这个例子中，我们肯定去index7，他能直接助力你去14号点，直接抵达终点。farthest会直接更新为14，意思是你走下一步，最远可以到达14号点
 * 并且在i==end（当前这一步遍历完了）时，会把farthest赋值给end
 *
 * 但是我们其实不会关心当前这一步我的落脚点会是在哪，
 * 我们只关心下一步我们最远可以到达哪里，不会关心谁让我们跑的最远，反正当前这一步都跑不脱[i,end]的范围。
 *
 * 整个代码逻辑是啥呢？
 * 举个例子，在这个样例中，假如我们已经跨出了第一步，那么我们第一步可以落脚的范围为[1,7]
 * 此时end就是7
 * 这个时候我i依次向后遍历，不断更新farthest，总有一个时刻我会遍历到end，意味着我当前这一步已经检查完了，我已经知道了下一步我可以去的最远的地方
 * 这个时候我就要把farthest赋值给end，让step++，表示我们进入了下一步。下一步能跳的最远范围是end。如果farthest已经大于终点了，那我们直接返回step。
 *
 */

public class Solution45 {
    public int jump(int[] nums) {
        //表示在第step步，我们能够落脚的范围
        int end = 0;
        //表示步数
        int steps = 0;
        //表示我们下一步可以去的最远范围
        int farthest = 0;

        for (int i = 0; i < nums.length; i++) {
            int newFarthest = nums[i]+i;
            if (newFarthest > farthest){
                farthest = newFarthest;
            }

            if (i == end){
                end = farthest;
                steps++;
                if (farthest == nums.length-1){
                    return steps;
                }
            }
        }

        return -1;

    }

    public static void main(String[] args) {
        int[] nums = new int[]{2,3,1,1,4};
        Solution45 solution45 = new Solution45();
        int jump = solution45.jump(nums);

    }
}
